package View.Almacen.BloquearUbicacion;

import java.io.*;
import java.util.Random;

public class VRP{
		final int Length = 300;
		final int MAX = 300;
		final int tSize = 2;

		int Size;
		int Source;
		int Destination;
		int Step;
		int Count;
		int Node;
		double Purity;
                Random rd;

		class RoutingClass{
			int chromosome [] = new int[Length];
			int size;
			double fitness;
		}
		RoutingClass Routing [] = new RoutingClass [2*MAX];
                RoutingClass BestRoute= new RoutingClass();

		private int Connect[][] = new int[Length][Length];      //Confirm Connection
		private int Temp_Connect[][] = new int[Length][Length]; //Tempairly Confirm Connection
		private int Cost[][] = new int[Length][Length];         //Cost Matrix
		private double Mutation_rate;							//Mutation Rate

		/////// To use Crossover Operation //////
		private class Cross{
			int x;
			int y;		
                }
                
                //20070263 el tamañao maximo de cross me preocupa
		private Cross cross[] = new Cross[Length*Length];

		private class TRouting{
			int chromosome[] = new int[Length];
			int size;
		}
		private TRouting tRouting[] = new TRouting[tSize];

		///
		VRP(int connect[][],int cost[][],int nodes,int size,int source,int destination){
                    Connect=connect;
                    Cost=cost;
                    Node=nodes;
                    Size=size;
                    Destination=destination;
                    for (int i=0;i<2*MAX;i++){
                        Routing[i]=new RoutingClass();
                    }
                    //20070263
                    for (int i=0;i<Length*Length;i++){
                        cross[i]= new Cross();
                    }
                    for (int i=0;i<tSize;i++){
                        tRouting[i]=new TRouting();
                    }
                    rd = new Random(System.currentTimeMillis());   
                    Mutation_rate = 0.1;
                    
                    Source=source;
                    Destination=destination;

		};

		int iRandom(int num){
			int temp = rd.nextInt(num);
			return temp;
		}      // int Random generator

		double dRandom()
		{
			double temp = rd.nextDouble();
			return temp;
		}   // Double Random generator
		/////// Initionalize Population ////////

		RoutingClass Init(){
			int flag;
                        Count = 0;

                        for(int i=0;i<Size;i++)
                                //Population(i);
                            if (Population(i)==-1)i--;
                        while(true)
                        {
                                flag = Convergence();
                                Fitness_Function();

                                //mejorRuta
                                int bestPosition=0,m;
                                for (m=1; m<Size;m++)
                                {
                                    if (Routing[m].fitness>Routing[bestPosition].fitness){
                                        bestPosition=m;
                                    }
                                }
                                if (Routing[bestPosition].fitness>BestRoute.fitness)
                                {
                                    BestRoute.fitness=Routing[bestPosition].fitness;
                                    BestRoute.size=Routing[bestPosition].size;
                                    for (m=0; m<BestRoute.size;m++)
                                        BestRoute.chromosome[m]=Routing[bestPosition].chromosome[m];
                                }
                                //fin mejor rura

                                if(flag == 0)
                                        break;
                        }
                        
                        return BestRoute;
		}

                void TTemp(int chromosome_number){
			for(int i=0;i<Node;i++)
			{
				Routing[chromosome_number].chromosome[i] = 0;
				for(int j=0;j<Node;j++)
					Temp_Connect[i][j] = Connect[i][j];
			}
		}

		int Population(int chromosome_number){
			int temp=0,locus;
			int length=0;
			TTemp(chromosome_number);
			int T[] = new int[Length];
			locus=T[length]=Source; length++;
			for(int j=1;j<Node;j++)
			{
				temp = pLocation(locus);
				if(temp != -1)
				{
					T[length]=temp;length++;
					Delete_Path(locus);
					locus = temp;
				}
				if(temp == Destination)
				{
					int i;
					for(i=0;i<length;i++)
						Routing[chromosome_number].chromosome[i] = T[i];
					Routing[chromosome_number].size = length;
                                        return 1;
					//break;
				}
			}
			if(temp != Destination)
				//Population(chromosome_number);
                            return -1;
                        return 1;
		} // Make Random Population

		int pLocation(int locus){
			int temp;
                        //contar conectividades;
                        int cont=0;
                        for (int i=0;i<Node;i++){
                            if (Temp_Connect[locus][i]==1)
                                cont++;
                        }
			if (cont==0)
                            return -1;
                        
                        temp = iRandom(cont);
                        int j=-1;
                        for (int i=0;i<Node;i++){
                            if (Temp_Connect[locus][i]==1)
                                j++;
                            if (j==temp)
                                return i;
                        }
                        return -1;
		}

		

		void Delete_Path(int locus)
		{
			for(int i=0;i<Node;i++)
			{
				Temp_Connect[i][locus] = Temp_Connect[locus][i] = 0 ;
			}
		}

		/////// Fitness Function ///////////
		void Fitness_Function()
		{
			double temp;
			for(int i=0;i<Size;i++)
			{
				temp = 0.0;Routing[i].fitness=0.0;
				for(int j=1;j<Routing[i].size;j++)
					temp += Cost[Routing[i].chromosome[j-1]][Routing[i].chromosome[j]];
				Routing[i].fitness += 1/temp;
			}
		}

		/////// Tournament Selection //////////
		void Shuffle()
		{
			int temp1, temp2;
			for(int i=0; i<Size; i++ )
			{
				temp1 = iRandom(Size);temp2 = iRandom(Size);
				Exchange(temp1,temp2);
			}
		}

		void Exchange(int first, int second)
		{
			Routing[MAX] = Routing[first];
			Routing[first] = Routing[second];
			Routing[second] = Routing[MAX];
		}
                void Tournament_Selection()
		{
			int i;
			Shuffle();
			for(i=0;i<Size/2;i++)
				Max(i,Size/2+i);
			for(i=0;i<Size;i++)
				Routing[i] = Routing[MAX+i];
			Count = 0;
		}
                void Max(int first,int second)
		{
			int temp = iRandom(Size);
			if(Routing[first].fitness >= Routing[second].fitness)
				Routing[MAX+Count] = Routing[first];
			else
				Routing[MAX+Count] = Routing[second];
			Count++;
			Routing[MAX+Count] = Routing[temp];
			Count++;
		}
		/////// Crossover /////////
		void Crossover(){
			int i;
			Shuffle();
			for(i=0;i<Size/2;i++)
				Crosspoint(i,Size/2+i);
		}

		void Crosspoinit_Init()
		{
			for(int i=0;i<MAX;i++)
				cross[i].x = cross[i].y = 0;
		}

		void Crosspoint(int first,int second){
			int num = -1; int sp;
			Crosspoinit_Init();
			for(int i=1;i<Routing[first].size-1;i++)
			{
				for(int j=1;j<Routing[second].size-1;j++)
				{
					if(Routing[first].chromosome[i] == Routing[second].chromosome[j])
					{
						num++;                                                
						cross[num].x =i;
						cross[num].y =j;
					}
				}
			}
			if(num != -1)
			{
				sp = iRandom(num+1);
				Crossover1(first,second,sp);                 
				Crossover2(first,second,sp);                                
				cCrossInit(first,second);
			}
		}

		void Crossover1(int first,int second,int crosspoint)
		{
			int i;
			int num =0;
			int s1 = cross[crosspoint].x;int s2 = cross[crosspoint].y;
			for(i=0;i<=s1;i++)
			{
                                tRouting[0].chromosome[num] = Routing[first].chromosome[i];
				num++;
			}
			for(i=s2+1;i<Routing[second].size;i++)
			{                                
				tRouting[0].chromosome[num] = Routing[second].chromosome[i];
				num++;
			}
			tRouting[0].size = num;
		}//First Corssover

		void Crossover2(int first,int second,int crosspoint){
			int i;
			int num =0;
			int s1 = cross[crosspoint].x;int s2 = cross[crosspoint].y;
			for(i=0;i<=s2;i++)
			{
				tRouting[1].chromosome[num] = Routing[second].chromosome[i];
				num++;
			}
			for(i=s1+1;i<Routing[first].size;i++)
			{
                                tRouting[1].chromosome[num] = Routing[first].chromosome[i];
				num++;
			}
			tRouting[1].size = num;
                        
		}//Second Crossover

		void cCrossInit(int first,int second)
		{
			int i;
			for(i=0;i<Node;i++)
				Routing[first].chromosome[i] = Routing[second].chromosome[i] = 0;

			for(i=0;i<tRouting[0].size;i++)
				Routing[first].chromosome[i] = tRouting[0].chromosome[i];
			Routing[first].size=tRouting[0].size;

			for(i=0;i<tRouting[1].size;i++)
				Routing[second].chromosome[i] = tRouting[1].chromosome[i];
			Routing[second].size=tRouting[1].size;

                        //20070263 calculo nuevamente el fitness,se puede optimizar
                        
			for(i=0;i<Node;i++)
			{
				tRouting[0].chromosome[i]=tRouting[1].chromosome[i]=0;
			}
		}//Tempairly Init

                void Recovery()
		{
			int i,j,k = 0;
			int flag = 0;
			for(i=0;i<Size;i++)
			{
				for(j=1;j<Routing[i].size;j++)
				{
					for(k=Routing[i].size-2;k>j;k--)
					{
						if(Routing[i].chromosome[j] == Routing[i].chromosome[k])
						{
							flag = -1;
							break;
						}
					}
					if(flag == -1)
						break;
				}
				if(flag == -1)
					reCombination(i,j,k);
				flag=0;
			}
		}
                void reCombination(int number,int first, int second)
		{
			int i;
			int temp[] = new int[Length];
			int num = 0;
			for(i=0;i<=first;i++)
			{
				temp[num] = Routing[number].chromosome[i];
				num++;
			}
			for(i=second+1;i<Routing[number].size;i++)
			{
				temp[num] = Routing[number].chromosome[i];
				num++;
			}
			Routing[number].size = num;
			for(i=0;i<Node;i++)
				Routing[number].chromosome[i] = 0;
			for(i=0;i<num;i++)
				Routing[number].chromosome[i] = temp[i];
		}

		/////// Mutuation ////////
		void Mutuation(){
			int C,sm;int flag;
			double rate=0.0;
			for(int i=0;i<Size;i++)
			{
				rate = dRandom();
				if(rate <= Mutation_rate )
				{
					C = i;
					flag = Routing[C].size;
					sm = iRandom(flag);
					mTTemp(C,sm);
					mPopulation(C,sm);
				}
			}
		}

                void mTTemp(int chromosome_number,int sm){
			int i,j;
			for(i=0;i<Node;i++)
			{
				for(j=0;j<Node;j++)
					Temp_Connect[i][j] = Connect[i][j];
			}
			for(i=0;i<sm;i++)
				Delete_Path(Routing[chromosome_number].chromosome[i]);
			Delete_Path(sm+1);
		}

		void mPopulation(int chromosome_number,int sm)
		{
			int temp=0,locus;
			int length=0;
			int T[] = new int[Length];
			locus=Routing[chromosome_number].chromosome[sm];
			for(int j=sm+1;j<Node+sm+1;j++)
			{
				temp = pLocation(locus);
				if(temp != -1)
				{
					T[length]=temp;length++;
					Delete_Path(locus);
					locus = temp;
				}
				if(temp == Destination)
				{
					int i;
					for(i=sm+1;i<Routing[chromosome_number].size;i++)
						Routing[chromosome_number].chromosome[i] = 0;
					for(i=0;i<length;i++)
						Routing[chromosome_number].chromosome[sm+i+1] = T[i];
					Routing[chromosome_number].size = sm+length+1;
					break;
				}
			}
			if(temp != Destination)
				while (Population(chromosome_number)==-1);
		}// Make Random Population

		////// Detect Convergence ////
		int Convergence()
		{
			int flag=0;
			Fitness_Function();
			Tournament_Selection();
			for(int i=1;i<Size;i++)
			{
				if(Routing[0].fitness != Routing[i].fitness)
				{
						flag++;
						break;
				}
			}
			if(flag != 0)
			{
				Crossover();
				Recovery();
				Mutuation();
			}
			return flag;
		}

		

		///// Everything Init ////
		void Routing_Init(){
			for(int i=0;i<Size*2;i++)
			{
				Routing[i].size = 0;
				Routing[i].fitness = 0.0;
				for(int j=0;j<Length;j++)
					Routing[i].chromosome[j] = 0;
			}
		}
}
